package 第六周;

/*
 * @author  YxinMiracle
 * @date  2022-05-05 14:23
 * @Gitee: https://gitee.com/yxinmiracle
 */

public class 不同路径2 {

    public int[][] obstacleGrid;
    public int[][] count;
    public int xLength;
    public int yLength;
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        this.obstacleGrid = obstacleGrid;
        count = new int[obstacleGrid.length][obstacleGrid[0].length];
        this.xLength = obstacleGrid.length;
        this.yLength = obstacleGrid[0].length;
        return dp(0,0);
    }

    private int dp(int x, int y) {
        if (x >= this.xLength || y>=this.yLength) return 0;
        if (count[x][y] != 0) return count[x][y];
        if (this.obstacleGrid[x][y] == 1) return 0; // 遇到障碍物
        if (x == this.xLength - 1 && y == this.yLength - 1) return 1;
        count[x][y] = dp(x+1,y) + dp(x,y+1);
        return count[x][y];
    }


}
